/**
 * //给定一个二叉树，检查它是否是镜像对称的。
 * //
 * //
 * //
 * // 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * //
 * //     1
 * //   / \
 * //  2   2
 * // / \ / \
 * //3  4 4  3
 * //
 * //
 * //
 * //
 * // 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * //
 * //     1
 * //   / \
 * //  2   2
 * //   \   \
 * //   3    3
 * //
 * //
 * //
 * //
 * // 进阶：
 * //
 * // 你可以运用递归和迭代两种方法解决这个问题吗？
 * // Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1608 👎 0
 */

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class ID00101SymmetricTree {
    public static void main(String[] args) {
        Solution solution = new ID00101SymmetricTree().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    /*
     * @Desc: 迭代解法
     * @Author vincentML
     * @Date: 2021/11/18 21:17
     * @param null
     * @return null
     */
    class Solution {
        boolean result = true;

        public boolean isSymmetric(TreeNode root) {
            if (root == null) return result;
            //双指针,双端队列遍历
            Deque<TreeNode> searchQueue = new ArrayDeque<TreeNode>();
            Deque<TreeNode> nextLevelQueue = new ArrayDeque<TreeNode>();
            //从左到右依次加入左右节点
            result = addNextQueue(nextLevelQueue, root.left, root.right);

            while (result && !nextLevelQueue.isEmpty()) {
                searchQueue = nextLevelQueue; //开始循环对比这一层
                nextLevelQueue = new ArrayDeque<TreeNode>(); //下一层新建一个队列
                while (result && !searchQueue.isEmpty()) {
                    TreeNode leftNode = searchQueue.pollFirst();
                    TreeNode rightNode = searchQueue.pollLast();

                    if (leftNode.val != rightNode.val) return false;

                    //都不为空，就加入下一层
                    //保持对称的,按照顺序加入下一层

                    result = addNextQueue(nextLevelQueue, leftNode.right, rightNode.left);
                    result = addNextQueue(nextLevelQueue, leftNode.left, rightNode.right);

                }

            }


            return result;


        }

        public boolean addNextQueue(Deque<TreeNode> nextLevelQueue, TreeNode left, TreeNode right) {
            if (left != null && right != null) {
                nextLevelQueue.addFirst(left);
                nextLevelQueue.addLast(right);
            } else if (left != null || right != null) {
                return false;
            }

            return result;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

    /*
     * @Desc: 递归解法
     * @Author vincentML
     * @Date: 2021/11/18 21:17
     * @param null
     * @return null
     */
    class Solution2 {
        boolean result = true;

        public boolean isSymmetric(TreeNode root) {
            if (root == null) return result;
            //根节点不用交换遍历
            return deepSearch(root.left, root.right);


        }

        public boolean deepSearch(TreeNode node1, TreeNode node2) {
            if (!result) return result; //深度优先，一旦发现不平衡就剪枝
            if (node1 == null && node2 == null) {
                return result; //都是空就返回true
            } else if (node1 != null && node2 == null) { //单边为null就是false；
                return false;
            } else if (node2 != null && node1 == null) { //单边为null就是false；
                return false;
            }
            //前序判断
            if (node1.val != node2.val) {//两者不等返回false；
                result = false;
                return result;
            }
            result = deepSearch(node1.left, node2.right);
            result = deepSearch(node1.right, node2.left);

            return result;
        }

    }


}